import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution103 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static class pair{
        int deep;
        TreeNode node;

        public pair(int deep, TreeNode node) {
            this.deep = deep;
            this.node = node;
        }
    }

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (root==null){
            return new ArrayList<>();
        }
        Queue<pair> queue=new LinkedList<>();
        List<List<Integer>> ans=new ArrayList<>();
        queue.add(new pair(0,root));
        List<Integer> temp=new ArrayList<>();
        int cur=0;
        while (!queue.isEmpty()){
            pair pair=queue.poll();
            int deep=pair.deep;
            TreeNode node=pair.node;
            if (deep!=cur){
                cur++;
                ans.add(temp);
                temp=new ArrayList<>();
            }
            temp.add(node.val);
            if (node.left!=null){
                queue.offer(new pair(deep+1,node.left));
            }
            if (node.right!=null){
                queue.offer(new pair(deep+1,node.right));
            }
        }
        ans.add(temp);
        for (int i=0;i<ans.size();i++){
            if (i%2==1){
                List<Integer> list=new ArrayList<>();
                for (int j=ans.get(i).size()-1;j>=0;j--){
                    list.add(ans.get(i).get(j));
                }
                ans.set(i,list);
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        TreeNode treeNode=new TreeNode(3,new TreeNode(9),new TreeNode(20,new TreeNode(15),new TreeNode(7)));
        System.out.println(new Solution103().zigzagLevelOrder(treeNode));
    }
}
